/*
提交链接：https://leetcode.cn/problems/longest-increasing-subsequence/submissions/562541884
300. 最长递增子序列-中等
完成日期：2024/9/8
线性dp
*/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> dp(n, 1);  // 初始化 dp 数组，每个位置的默认值为 1
        // 动态规划计算最长递增子序列的长度
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {  // 如果当前元素比之前的元素大
                    dp[i] = max(dp[i], dp[j] + 1);  // 更新 dp[i] 的值
                }
            }
        }
        // dp 数组中的最大值即为最长递增子序列的长度
        return *max_element(dp.begin(), dp.end());
    }
};